package com.example.demo.leetcode.jianzhi;

/**
 * @author xujimou
 * @version 2.0
 * @Description F(0) = 0,   F(1) = 1
 *              F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
 * @date 2021/6/3 18:15
 */
public class Int_斐波那契 {

    //缓存解法
    static int [] cache = new int [101];

    public static int fib(int n) {
        if(n<=0) return 0;
        if(n==1) return 1;
        int n1=0;
        int n2=0;
        if(n< 101 && cache[n-1]>0){
            n1 = cache[n-1];
        }
        if(n< 101 && cache[n-2]>0){
            n2 = cache[n-2];
        }
        cache[n] = ((n1>0?n1 : fib(n-1))+(n2>0?n2 : fib(n-2)) )%1000000007;
        return cache[n];

    }


    //动规解法
    public static int fib2(int n){

        int [] dp = new int[n+1];
        dp[0]=0;
        dp[1]=1;
        for(int i =2;i<=n;i++){
            dp[i] = dp[i-1] + dp[i-2];
            dp[i] = dp[i] % 1000000007;
        }
        return dp[n];
    }


    public static void main(String[] args) {
        System.out.println(fib(5));
    }
}
